import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestHeap {

//    private static final int K = ;
    public int[] elem;
    public int usedSize;

    public  TestHeap(){
        this.elem=new int[10];
    }

    public void  initElem(int[] array){
        for(int i = 0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }
//        Arrays.copyOf();

    }
//  小根堆的话修改一下大于小于号即可
//  ”创建大根堆“
    public void createHeap(){
        for(int parent = (usedSize-1-1)/2;parent>=0;parent--){
            shiftDown(parent,usedSize);
        }
    }

//      "向下调整"，父亲下标，每棵树结束的下标(时间复杂度T(N)=O(n))
    private  void  shiftDown(int parent,int len){
        int child = 2*parent+1;
//      最起码要有左孩子
        while (child<len){
//      一定是有右孩子的情况下
            if(child+1<len && elem[child]<elem[child+1]){
//      只是找到一棵树里面最大的子节点
                child++;
//      child下标  一定是左右孩子 最大值的下标
            }
            if(elem[child]>elem[parent]){
//      比较并换值
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

//      插入元素后 "向上调整" (时间复杂度为T(N)=N*logN)
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
//      插入元素，"向上调整"
    public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=val;
        shiftUp(usedSize-1);//10
    }
    public boolean isFull(){
        return  usedSize==elem.length;
    }

//      删除，因为堆的删除必须要从堆顶删除
    public void pop(){
        if(isEmpty()){
            return;
        }
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
    }
    public boolean isEmpty(){
        return  usedSize==0;
    }
    private void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    public int peek(){
        if(isEmpty()){
            return 0;
        }
        return elem[0];
    }
//      堆排序
    public void heapSort(){
        int end=usedSize-1;
        while (end>0){
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }









}
